package com.chapter4.graph.sp;

import java.util.Stack;

/**
 * 
* @ClassName: DirectWeightCycle 
* @Description: 判断有向图（带权重）是否有环 
* @author minjun
* @date 2015年3月14日 下午7:50:17 
*
 */
public class DirectWeightCycle {

	private boolean[] marked;
	
	private Stack<Integer> cycle;
	
	private boolean[] onStack;
	
	private int[] edgeTo;
	
	public DirectWeightCycle(DirectWeightGraph g){
		marked=new boolean[g.V()];
		edgeTo=new int[g.V()];
		onStack=new boolean[g.V()];
		for(int i=0;i<g.V();i++){
			if(!marked[i]){
				dfs(g,i);
			}
		}
	}
	
	private void dfs(DirectWeightGraph g, int v) {
		marked[v]=true;
		onStack[v]=true;
		for(DirectEdge e:g.adj(v)){
			int w=e.to();
			if(!marked[w]){
				edgeTo[w]=v;
				dfs(g, w);
			}else if(onStack[w]){
				cycle=new Stack<Integer>();
				for(int i=v;i!=w;i=edgeTo[i]){
					cycle.push(i);
				}
				cycle.push(w);
				cycle.push(v);
			}
		}
		onStack[v]=false;
	}

	public boolean hasCycle(){
		return cycle!=null;
	}
	
	public Iterable<Integer> cycle(){
		return cycle;
	}
}
